package 动态规划.组合求和系列;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/5/25 15:44
 */
public class lc377组合求和4 {
    public int combinationSum4(int[] nums, int target) {
        /*
        组合问题的 排列 卧槽


         */
        /*
        index : 0 ~ len
         */
        int dp[] = new int[target + 1];
        Arrays.fill(dp, -1);
        return f(0, nums, target, dp);
    }

    /*
    nums 中全是 正数， 如果 有 0  和 负数的话， basecase的情况又稍微 有些特殊
     */
    public int f(int index, int nums[], int rest, int dp[]) {
        if (rest == 0) {
            return 1;
        }
        if (dp[rest] != -1) {
            return dp[rest];
        }
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            if (rest - nums[i] >= 0) {
                ans += f(index, nums, rest - nums[i], dp);
            }
        }
        return dp[rest] = ans;
    }


    public int solution(int nums[],int target){
        int dp [] = new int[target + 1];
        dp[0] = 1;
        for(int rest = 1;rest <= target; rest++){
            for(int i = 0;i < nums.length;i++){
                if(rest - nums[i] >= 0){
                    dp[rest] += dp[rest - nums[i]];
                }
            }
        }
        return dp[target];
    }
}
